package com.atguigu.Prim;

import java.util.Arrays;

/**
 * @author tbwtbw
 * @create 2021-11-26 15:12
 */
public class primAlgorithm {
    public static void main(String[] args) {

        char[] data = new char[]{'A','B','C','D','E','F','G'};
        int numOfVertices = data.length;
        //邻接矩阵的关系使用二维数组表示,10000这个大数，表示两个点不联通
        int [][] weight=new int[][]{
                {10000,5    ,7    ,10000,10000,10000,2    },
                {5    ,10000,10000,9    ,10000,10000,3    },
                {7    ,10000,10000,10000,8    ,10000,10000},
                {10000,9    ,10000,10000,10000,4    ,10000},
                {10000,10000,8    ,10000,10000,5    ,4    },
                {10000,10000,10000,4    ,5    ,10000,6    },
                {2    ,3    ,10000,10000,4    ,6    ,10000}
        };

        MGraph graph = new MGraph(numOfVertices);
        MST mst = new MST();
        mst.createGraph(graph,data,weight);
//        mst.showGraph(graph);
        mst.prim(graph,1);
    }
}

class MST {

    public void createGraph(MGraph graph, char data[], int[][] weight) {
        int i, j;
        for(i = 0; i < graph.numOfVertices; i++) {//顶点
            graph.data[i] = data[i];
            for(j = 0; j < graph.numOfVertices; j++) {
                graph.weight[i][j] = weight[i][j];
            }
        }
    }

    //显示图的邻接矩阵
    public void showGraph(MGraph graph) {
        for(int[] link: graph.weight) {
            System.out.println(Arrays.toString(link));
        }
    }

    public void prim(MGraph graph, int start){

        int[] isVisited = new int[graph.numOfVertices];
        int minTrace = 10000;//一个顶点到另一个顶点的最小权值
        isVisited[start] = 1;
        int v1 = -1;
        int v2 = -1;//表示成功路径的两个顶点

        for (int i = 1; i < graph.numOfVertices; i++) {//表示成功的边数，最少的边为顶点数-1
            for (int j = 0; j < graph.numOfVertices; j++) {//最小子图的顶点
                if (isVisited[j] == 1){ //最小子图里没有的点就不要进去了
                    for (int k = 0; k < graph.numOfVertices; k++) {//表示寻找邻接点
                        if (isVisited[k] == 0 && graph.weight[j][k] < minTrace){
                            minTrace = graph.weight[j][k];
                            v1 = j;
                            v2 = k;
                        }
                    }//从这个for里出来就说明顶点j找到了自己能连的最短的路径,接下来遍历完最小子图中其他的顶点
                }
            }//从这个for里出来的 minTrace 就是最小子图能接触的的最小路径
            System.out.println("<" + graph.data[v1] + "," + graph.data[v2] + "> 权值为 ： " + graph.weight[v1][v2]);
            isVisited[v2] = 1;
            minTrace = 10000;
        }
    }
}

class MGraph {
    int numOfVertices;
    char[] data;//顶点值
    int[][] weight;//邻接矩阵，存的是权值

    public MGraph(int numOfVertices) {
        this.numOfVertices = numOfVertices;
        data = new char[numOfVertices];
        weight = new int[numOfVertices][numOfVertices];
    }
}
